1 /*
2 * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 *
8 * - Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 *
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * - Neither the name of Oracle nor the names of its
16 * contributors may be used to endorse or promote products derived
17 * from this software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
20 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
21 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
26 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
27 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
28 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
29 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 import java.util.Arrays;
33 import java.util.Random;
34
35 import static java.lang.Integer.parseInt;
36
37 /**
38 * MergeExample is a class that runs a demo benchmark of the {@code ForkJoin} framework
39 * by benchmarking a {@link MergeSort} algorithm that is implemented using
40 * {@link java.util.concurrent.RecursiveAction}.
41 * The {@code ForkJoin} framework is setup with different parallelism levels
42 * and the sort is executed with arrays of different sizes to see the
43 * trade offs by using multiple threads for different sizes of the array.
44 */
45 public class MergeDemo {
46 // Use a fixed seed to always get the same random values back
47 private final Random random = new Random(759123751834L);
48 private static final int ITERATIONS = 10;
49
50 /**
51 * Represents the formula {@code f(n) = start + (step * n)} for n = 0 & n < iterations
52 */
53 private static class Range {
54 private final int start;
55 private final int step;
56 private final int iterations;
57
58 private Range(int start, int step, int iterations) {
59 this.start = start;
60 this.step = step;
61 this.iterations = iterations;
62 }
63
64 /**
65 * Parses start, step and iterations from args
66 * @param args the string array containing the arguments
67 * @param start which element to start the start argument from
68 * @return the constructed range
69 */
70 public static Range parse(String[] args, int start) {
71 if (args.length < start + 3) {
72 throw new IllegalArgumentException("Too few elements in array");
73 }
74 return new Range(parseInt(args[start]), parseInt(args[start + 1]), parseInt(args[start + 2]));
75 }
76
77 public int get(int iteration) {
78 return start + (step * iteration);
79 }
80
81 public int getIterations() {
82 return iterations;
83 }
84
85 @Override
86 public String toString() {
87 StringBuilder builder = new StringBuilder();
88 builder.append(start).append(" ").append(step).append(" ").append(iterations);
89 return builder.toString();
90 }
91 }
92
93 /**
94 * Wraps the different parameters that is used when running the MergeExample.
95 * {@code sizes} represents the different array sizes
96 * {@code parallelism} represents the different parallelism levels
97 */
98 private static class Configuration {
99 private final Range sizes;
100 private final Range parallelism;
101
102 private final static Configuration defaultConfig = new Configuration(new Range(20000, 20000, 10),
103 new Range(2, 2, 10));
104
105 private Configuration(Range sizes, Range parallelism) {
106 this.sizes = sizes;
107 this.parallelism = parallelism;
108 }
109
110 /**
111 * Parses the arguments and attempts to create a configuration containing the
112 * parameters for creating the array sizes and parallelism sizes
113 * @param args the input arguments
114 * @return the configuration
115 */
116 public static Configuration parse(String[] args) {
117 if (args.length == 0) {
118 return defaultConfig;
119 } else {
120 try {
121 if (args.length == 6) {
122 return new Configuration(Range.parse(args, 0), Range.parse(args, 3));
123 }
124 } catch (NumberFormatException e) {
125 System.err.println("MergeExample: error: Argument was not a number.");
126 }
127 System.err.println("MergeExample <size start> <size step> <size steps> <parallel start> <parallel step>" +
128 " <parallel steps>");
129 System.err.println("example: MergeExample 20000 10000 3 1 1 4");
130 System.err.println("example: will run with arrays of sizes 20000, 30000, 40000" +
131 " and parallelism: 1, 2, 3, 4");
132 return null;
133 }
134 }
135
136 /**
137 * Creates an array for reporting the test result time in
138 * @return an array containing {@code sizes.iterations * parallelism.iterations} elements
139 */
140 private long[][] createTimesArray() {
141 return new long[sizes.getIterations()][parallelism.getIterations()];
142 }
143
144 @Override
145 public String toString() {
146 StringBuilder builder = new StringBuilder("");
147 if (this == defaultConfig) {
148 builder.append("Default configuration. ");
149 }
150 builder.append("Running with parameters: ");
151 builder.append(sizes);
152 builder.append(" ");
153 builder.append(parallelism);
154 return builder.toString();
155 }
156 }
157
158 /**
159 * Generates an array of {@code elements} random elements
160 * @param elements the number of elements requested in the array
161 * @return an array of {@code elements} random elements
162 */
163 private int[] generateArray(int elements) {
164 int[] array = new int[elements];
165 for (int i = 0; i < elements; ++i) {
166 array[i] = random.nextInt();
167 }
168 return array;
169 }
170
171 /**
172 * Runs the test
173 * @param config contains the settings for the test
174 */
175 private void run(Configuration config) {
176 Range sizes = config.sizes;
177 Range parallelism = config.parallelism;
178
179 // Run a couple of sorts to make the JIT compile / optimize the code
180 // which should produce somewhat more fair times
181 warmup();
182
183 long[][] times = config.createTimesArray();
184
185 for (int size = 0; size < sizes.getIterations(); size++) {
186 runForSize(parallelism, sizes.get(size), times, size);
187 }
188
189 printResults(sizes, parallelism, times);
190 }
191
192 /**
193 * Prints the results as a table
194 * @param sizes the different sizes of the arrays
195 * @param parallelism the different parallelism levels used
196 * @param times the median times for the different sizes / parallelism
197 */
198 private void printResults(Range sizes, Range parallelism, long[][] times) {
199 System.out.println("Time in milliseconds. Y-axis: number of elements. X-axis parallelism used.");
200 long[] sums = new long[times[0].length];
201 System.out.format("%8s ", "");
202 for (int i = 0; i < times[0].length; i++) {
203 System.out.format("%4d ", parallelism.get(i));
204 }
205 System.out.println("");
206 for (int size = 0; size < sizes.getIterations(); size++) {
207 System.out.format("%8d: ", sizes.get(size));
208 for (int i = 0; i < times[size].length; i++) {
209 sums[i] += times[size][i];
210 System.out.format("%4d ", times[size][i]);
211 }
212 System.out.println("");
213 }
214 System.out.format("%8s: ", "Total");
215 for (long sum : sums) {
216 System.out.format("%4d ", sum);
217 }
218 System.out.println("");
219 }
220
221 private void runForSize(Range parallelism, int elements, long[][] times, int size) {
222 for (int step = 0; step < parallelism.getIterations(); step++) {
223 long time = runForParallelism(ITERATIONS, elements, parallelism.get(step));
224 times[size][step] = time;
225 }
226 }
227
228 /**
229 * Runs <i>iterations</i> number of test sorts of a random array of <i>element</i> length
230 * @param iterations number of iterations
231 * @param elements number of elements in the random array
232 * @param parallelism parallelism for the ForkJoin framework
233 * @return the median time of runs
234 */
235 private long runForParallelism(int iterations, int elements, int parallelism) {
236 MergeSort mergeSort = new MergeSort(parallelism);
237 long[] times = new long[iterations];
238
239 for (int i = 0; i < iterations; i++) {
240 // Suggest the VM to run a garbage collection to reduce the risk of getting one
241 // while running the test run
242 System.gc();
243 long start = System.currentTimeMillis();
244 mergeSort.sort(generateArray(elements));
245 times[i] = System.currentTimeMillis() - start;
246 }
247
248 return medianValue(times);
249 }
250
251 /**
252 * Calculates the median value of the array
253 * @param times array of times
254 * @return the median value
255 */
256 private long medianValue(long[] times) {
257 if (times.length == 0) {
258 throw new IllegalArgumentException("Empty array");
259 }
260 // Make a copy of times to avoid having side effects on the parameter value
261 Arrays.sort(times.clone());
262 long median = times[times.length / 2];
263 if (times.length > 1 && times.length % 2 != 0) {
264 median = (median + times[times.length / 2 + 1]) / 2;
265 }
266 return median;
267 }
268
269 /**
270 * Generates 1000 arrays of 1000 elements and sorts them as a warmup
271 */
272 private void warmup() {
273 MergeSort mergeSort = new MergeSort(Runtime.getRuntime().availableProcessors());
274 for (int i = 0; i < 1000; i++) {
275 mergeSort.sort(generateArray(1000));
276 }
277 }
278
279 public static void main(String[] args) {
280 Configuration configuration = Configuration.parse(args);
281 if (configuration == null) {
282 System.exit(1);
283 }
284 System.out.println(configuration);
285 new MergeDemo().run(configuration);
286 }
287 }